package com.zhupf.binaryTree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhupf
 * @date 2023年11月24日 14:09
 * @Description 104. 二叉树的最大深度
 */
public class MaxDepth {

    /**
     * 深度优先
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
    }

    /**
     * 广度优先
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root) {
        if(root == null){
            return 0;
        }
        Deque<TreeNode> stk = new LinkedList<>();
        int ans = 0;
        stk.push(root);
        while (!stk.isEmpty()){
            int size = stk.size();
            while (size != 0){
                TreeNode poll = stk.poll();
                if(poll.left != null){
                    stk.offer(poll.left);
                }
                if(poll.right != null){
                    stk.offer(poll.right);
                }
                size --;
            }
            ans ++;
        }
        return ans;
    }

}
